import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int array[] = {53,784,4,94,645,12};
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 基数排序法
     * @param array:输入数组
     */
    public static void radixSort(int[] array){
        int[][] bucket = new int[10][array.length];
        //bucketElementCount为桶中元素个数
        int[] bucketElementCount = new int[10];

        int max = array[0];
        for(int i = 0; i < array.length; i++){
            if(max < array[i]){
                max = array[i];
            }
        }

        int maxLength = (max + "").length();

        for(int i =0, n = 1; i < array.length; i++, n *=10){
            for(int j = 0; j < array.length; j++){
                //digitOfElement为元素不同位的值
                int digitOfElement = array[j] / n % 10;
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = array[j];
                bucketElementCount[digitOfElement]++;
            }

            int index = 0;
            for(int k = 0; k < bucketElementCount.length; k++){
                if(bucketElementCount[k] != 0){
                    for(int l = 0; l < bucketElementCount[k]; l++){
                        array[index++] = bucket[k][l];
                    }
                }
                bucketElementCount[k] = 0;
            }
        }
    }
}
